package oct2013.linkednode;

public class ConvertSortedListtoBinarySearchTree {
	public TreeNode sortedListToBST(ListNode head) {
		if (head == null)
			return null;
		ListNode cur = head;
		ListNode end = head;
		ListNode prev = null;
		while (end != null && end.next != null) {
			prev = cur;
			cur = cur.next;
			end = end.next.next;
		}
		TreeNode root = new TreeNode(cur.val);
		if (prev != null) {
			prev.next = null;
			root.left = sortedListToBST(head);
		}
		root.right = sortedListToBST(cur.next);
		return root;
	}
}
